package leetcode._08_dynic;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author pppppp
 * @date 2022/4/9 9:51
 * 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
 * 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
 * <p>
 * 示例 1：
 * 输入：s = "bbbab"
 * 输出：4
 * 解释：一个可能的最长回文子序列为 "bbbb" 。
 * <p>
 * 示例 2：
 * 输入：s = "cbbd"
 * 输出：2
 * 解释：一个可能的最长回文子序列为 "bb" 。
 * <p>
 * 提示：
 * 1 <= s.length <= 1000
 * s 仅由小写英文字母组成
 */
public class _516_最长回文子序列 {
    @Test
    public void T_0() {
        String[] s = {"aabaaba","abcdabcdabcdabcd","abaabaa","abcabcabcabc", "ababa", "bbbab", "cbbd"};
        int[] ans = {6,7,6,7, 5, 4, 2};
        for (int i = 0; i < s.length; i++) {
            // System.out.println(longestPalindromeSubseq_0(s[i]) == ans[i]);
            System.out.println(longestPalindromeSubseq_1(s[i]) == ans[i]);
        }
    }
    /*1.gf dp[i][j] = {dp[i+1][j-1]+2 Si = Sj,max{dp[i][j-1],dp[i+1][j]}}
    * 由状态转移方程确定遍历的顺序 从下往上 从左往右
    * */
    public int longestPalindromeSubseq_1(String s) {
        int n = s.length();
        char[] ch = s.toCharArray();
        int[][] dp = new int[n][n];
        for (int i = n-1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i+1; j < n; j++) {
                if(ch[i] == ch[j]){
                    dp[i][j] = dp[i+1][j-1] + 2;
                }else {
                    dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][n-1];
    }

    /*0.有较大的bug*/
    public int longestPalindromeSubseq_0(String s) {

        char[] ch = s.toCharArray();
        HashMap<Character, List<Integer>> map = new HashMap<>();
        HashMap<Character, List<Integer>> mapcopy = new HashMap<>();
        for (int i = 0; i < ch.length; i++) {
            if (map.containsKey(ch[i])) {
                List<Integer> list = map.get(ch[i]);
                list.add(i);
            } else {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(i);
                map.put(ch[i], list);
            }
        }
        for (Character character : map.keySet()) {
            mapcopy.put(character,new ArrayList<>(map.get(character)));
        }
        int l = 0, r = s.length() - 1, res = 0;
        /*从右开始匹配*/
        while (r > l) {
            List<Integer> list = map.get(ch[r]);
            boolean find = false;
            if (list.size() > 1) {
                for (Integer index : list) {
                    if(index >= l && index < r){
                        l = index;
                        list.remove(Integer.valueOf(l));
                        list.remove(Integer.valueOf(r));
                        res += 2;
                        l++;
                        r--;
                        find = true;
                        break;
                    }
                }
                if(!find){
                    r--;
                }

            }else {
                r--;
            }
            if (r - l == 1) {
                res = ch[l] == ch[r] ? res + 2 : ++res;
                break;
            } else if (r == l) {
                ++res;
                break;
            }
        }
        /*从左开始匹配*/
        l = 0;r = s.length() - 1;
        int res2 = 0;
        map = mapcopy;
        while (r > l) {
            List<Integer> list = map.get(ch[l]);
            if (list.size() > 1) {
                boolean find = false;
                for (int i = list.size()-1; i >= 0; i--) {
                    if(list.get(i) <= r && list.get(i) > l){
                        r = list.get(i);
                        list.remove(Integer.valueOf(l));
                        list.remove(Integer.valueOf(r));
                        res2 += 2;
                        l++;
                        r--;
                        find = true;
                        break;
                    }
                }
                if(!find){
                    l++;
                }
            }else {
                l++;
            }
            if (r - l == 1) {
                res2 = ch[l] == ch[r] ? res2 + 2 : ++res2;
                break;
            } else if (r == l) {
                ++res2;
                break;
            }
        }

        return Math.max(res,res2) > 0 ? Math.max(res,res2) : 1;
    }
}
